package com.yiwenup.leetcode.offer;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
 **/
public class No039 {
    /**
     * 执行用时：17 ms, 在所有 Java 提交中击败了16.85%的用户
     * 内存消耗：43.6 MB, 在所有 Java 提交中击败了52.49%的用户
     */
    public int majorityElement(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num)) {
                int count = map.get(num);
                if (count >= (length >> 1)) {
                    return num;
                } else {
                    map.put(num, count + 1);
                }
            } else {
                map.put(num, 1);
            }
        }
        return -1;
    }

    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了99.97%的用户
     * 内存消耗：43.9 MB, 在所有 Java 提交中击败了39.84%的用户
     */
    public int majorityElement2(int[] nums) {
        int vote = 0, cur = 0;

        for (int num : nums) {
            if (vote == 0) cur = num;
            vote += cur == num ? 1 : -1;
        }

        return cur;
    }
}
